package com.gxc.array;


/**
 * 给定一个整数数组A，长度为n，有 1 <= A[i] <= n，且对于[1,n]的整数，
 * 其中部分整数会重复出现而部分不会出现。
 * 实现算法找到[1,n]中所有未出现在A中的整数。
 * 提示:尝试实现0(n)的时间复杂度和0(1)的空间复杂度(返回值不计入空间复杂)。
 * 输入描述:
 * 一行数字，全部为整数，空格分隔
 * A0 A1 A2 A3...
 * 输出描述:
 * 一行数字，全部为整数，空格分隔RO R1 R2 R3...
 * 示例1:
 * 输入
 * 1 3 4 3
 * 输出
 * 2
 *
 * 解法：
 * 数组长度n，数组内数据 1 <= A[i] <= n，数据内排序即可，满足 i位置的数 = i+1
 */
public class Exclude {

    public static void main(String[] args) {
        int[] randArr = new int[]{1,3,4,3,6,6};
        exclude(randArr);
    }

    public static void exclude(int[] arr) {
        if (arr == null || arr.length == 0) return;

        int i = 0;
        while (i<arr.length) {
            if (arr[i]!=0 && arr[i] != i+1) {
                swapNum(arr, i, arr[i] - 1);
            } else {
                i++;
            }
        }

        for (i = 0; i < arr.length; i++) {
            if (arr[i] != i+1) {
                System.out.print(i+1 + " ");
            }
        }
    }

    /**
     * 交换当前位置和目标位置，使所有位置 arr[i] = i+1
     * 如果原位置已经符合  arr[i] = i+1，则当前位置边0
     * @param arr
     * @param i
     * @param j
     */
    private static void swapNum(int[] arr, int i, int j) {
        if (arr[j] == j+1) {
            arr[i] = 0;
            return;
        }

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
